package leetcode_题库;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.atomic.AtomicBoolean;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/22 16:15 星期一
 */
public class _36_有效的数独 {

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}};

//        board = new char[][]{
//                {'.', '1', '.', '5', '2', '.', '.', '.', '.'},
//                {'.', '.', '.', '.', '.', '6', '4', '3', '.'},
//                {'.', '.', '.', '.', '.', '.', '.', '.', '.'},
//                {'5', '.', '.', '.', '.', '.', '9', '.', '.'},
//                {'.', '.', '.', '.', '.', '.', '.', '5', '.'},
//                {'.', '.', '.', '5', '.', '.', '.', '.', '.'},
//                {'9', '.', '.', '.', '.', '3', '.', '.', '.'},
//                {'.', '.', '6', '.', '.', '.', '.', '.', '.'},
//                {'.', '.', '.', '.', '.', '.', '.', '.', '.'}};
        System.err.println(isValidSudoku(board));
//        System.err.println(isValidSudokuFuck(board));
    }

    /**
     * 力扣评论解法
     * > 2022/08/23 10:13:58
     * 解答成功:
     * 	执行耗时:1 ms,击败了99.26% 的Java用户
     * 	内存消耗:41.1 MB,击败了89.76% 的Java用户
     * @param board
     * @return
     */
    private static boolean isValidSudoku(char[][] board) {
        //存储x行上字符n是否出现：row[0][7] = true,第一（0）行上字符'8'（因为下面有减去'1'）存在
        boolean[][] row = new boolean[9][9];
        //存储y列上字符n是否出现
        boolean[][] col = new boolean[9][9];
        //存储九宫格中字符n是否出现
        boolean[][] block = new boolean[9][9];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.'){
                    //非有效字符，continue
                    continue;
                }
                //题干要求字符介于'1'~'9'，字符减去字符'1'能变成int，也就是0~8
                int num = board[i][j] - '1';
                //这么写可以利用空间，九宫格一共包含九个小九宫格，i/3*3控制的是从左到右三个块，j/3控制的是从上到下三个块
                //若i=5，j=5，那么从上到下排列来看，该坐标位于第4块（从0开始）
                int blockIndex = i / 3 * 3 + j / 3;
                //若行、列、小九宫格内出现该字符的num，false
                if (row[i][num] || col[j][num] || block[blockIndex][num]){
                    return false;
                }
                //记录
                row[i][num] = true;
                col[j][num] = true;
                block[blockIndex][num] = true;
            }
        }
        return true;
    }


    /**
     * 自己写的勾吧算法
     * > 2022/08/23 09:52:28
     * 解答成功:
     * 执行耗时:5 ms,击败了6.74% 的Java用户
     * 内存消耗:41.3 MB,击败了70.41% 的Java用户
     * > 2022/08/23 09:52:28
     * @param board
     * @return
     */
    public static boolean isValidSudokuFuck(char[][] board) {
        //定义哈希表，key为每一项数独中的字符，val为每一项数独对应的角标Map（存储坐标键值对）
        //其中，HashMap<Integer, Set<Integer>>，横坐标为Integer x，纵坐标为Set<Integer> Y，坐标点为（x,Y(n)）
        HashMap<Character, HashMap<Integer, Set<Integer>>> map = new HashMap<>(board.length);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                //遍历，记录每一点，存储为item
                char item = board[i][j];
                if (item == '.') {
                    //若非有效字符，continue
                    continue;
                }
                //判断横轴是否有重复元素
                if (map.containsKey(item) && map.get(item).containsKey(i)) {
                    //若map中包含item这个键，说明put过了。且之前的键集合对应坐标的横坐标包含当前i，说明新插入的相同元素和之前插入的在同一行。违背规则
                    return false;
                }
                //定义原子isF，来判断纵轴是否有重复元素，即包含j
                AtomicBoolean isF = new AtomicBoolean(false);
                int finalJ = j;
                //防止空指针，若map有值且map包含该键，则继续
                if (map.size() > 0 && map.get(item)!= null) {
                    map.get(item).forEach((k, v) -> {
                        //遍历map中键为item的所有横坐标，若对应Set类型纵坐标哈希表中包含finalJ，说明同一列上出现了相同元素，违背规则。
                        if (v.contains(finalJ)) {
                            isF.set(true);
                        }
                    });
                    if (isF.get()) {
                        return false;
                    }
                }
                //接下来，我们判断在当前元素所在的小九宫格上是否有重复
                int blockX = i / 3;
                int blockY = j / 3;
                //除三再乘三，比如8/3*3就得到6，也就是第三块的左边界，右边界+3即可，遍历，若坐标x,y对应元素是item且坐标不一样，说明小九宫格内出现了相同元素，违背规则
                for (int x = blockX * 3; x < (blockX + 1) * 3; x++) {
                    for (int y = blockY * 3; y < (blockY + 1) * 3; y++) {
                        if (board[x][y] == item && x != i && y != j) {
                            return false;
                        }
                    }
                }
                //若map中有这个key，我们取出坐标哈希表，否则new一个
                HashMap<Integer, Set<Integer>> position = map.size() > 0 && map.get(item)!= null ? map.get(item):new HashMap<>(1);
                //若坐标集中，横坐标为x对应的Y坐标不为空，取出，否则new一个
                Set<Integer> set = position.get(i)!=null? position.get(i) : new HashSet<>();
                //存储y坐标
                set.add(j);
                //存储x坐标并put到坐标哈希表
                position.put(i, set);
                //将新的坐标哈希表存储到map中
                map.put(item, position);
            }
        }
        return true;
        /*

            > 2022/08/23 09:52:28
            解答成功:
                执行耗时:5 ms,击败了6.74% 的Java用户
                内存消耗:41.3 MB,击败了70.41% 的Java用户
                        > 2022/08/23 09:52:28

         */
    }
}
